package leetcode;

import java.math.BigDecimal;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Code002_MedianFinder {

    public PriorityQueue<Integer> minQueue;
    public PriorityQueue<Integer> maxQueue;
    public Code002_MedianFinder(){
        minQueue = new PriorityQueue<>();
        maxQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
    }

    public void addNum(int num){

        if(maxQueue.isEmpty() && minQueue.isEmpty()){
            maxQueue.add(num);
        }else{
            if(num <= maxQueue.peek()){
                maxQueue.add(num);
            }else{
                minQueue.add(num);
            }
        }

        if(minQueue.size() - maxQueue.size() == 2){
            maxQueue.add(minQueue.poll());
        }else if(minQueue.size() - maxQueue.size() == -2){
            minQueue.add(maxQueue.poll());
        }

    }

    public double findMedian(){
        if(minQueue.size() == maxQueue.size()){

            return (maxQueue.peek() + minQueue.peek()) / 2.0;
        }else if(minQueue.size() > maxQueue.size()){
            return minQueue.peek();
        }else{
            return maxQueue.peek();
        }
    }

    public static void main(String[] args) {
        Code002_MedianFinder mf = new Code002_MedianFinder();
        mf.addNum(5);
        mf.addNum(3);
        mf.addNum(7);
        mf.addNum(4);
        double a = mf.findMedian();
        System.out.println(mf.findMedian());
    }
}
